package com.guaoran.algorithm.binary.tree;

import com.guaoran.algorithm.common.CommonUtil;
import com.guaoran.algorithm.entity.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @Auth gucheng
 * @Desc 序列化和反序列化二叉树
 * https://leetcode.com/problems/serialize-and-deserialize-binary-tree/
 * @Date 2021/1/20 上午10:03
 */
public class SerializeAndDeserializeBinaryTree {
    public static void main(String[] args) {
        TreeNode treeNode = CommonUtil.createTreeNode(new Integer[]{1, 2, 3, null, null, 4, 5});
        System.out.println(CommonUtil.readTreeNode(treeNode));
        String serialize = serialize(treeNode);
        TreeNode deserialize = deserialize(serialize);
        System.out.println(CommonUtil.readTreeNode(deserialize));
    }

    // Encodes a tree to a single string.
    public static String serialize(TreeNode root) {
        if(root == null){
            return null;
        }
        List<TreeNode> list = new ArrayList<>();
        list.add(root);
        for (int i = 0; i < list.size(); i++) {
            TreeNode treeNode = list.get(i);
            if(treeNode == null){
                continue;
            }
            list.add(treeNode.left);
            list.add(treeNode.right);
        }

        while(list.get(list.size()-1) == null){
            list.remove(list.size()-1);
        }

        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < list.size(); i++) {
            TreeNode treeNode = list.get(i);
            if(treeNode == null){
                sb.append("null");
            }else{
                sb.append(treeNode.val);
            }
            if(i != list.size() -1){
                sb.append(",");
            }
        }
        sb.append("]");

        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public static TreeNode deserialize(String data) {
        if(data == null || data.length() == 0 || data.equals("[]")){
            return null;
        }
        String[] arr = data.substring(1, data.length() - 1).split(",");
        TreeNode root = new TreeNode(Integer.parseInt(arr[0]));
        List<TreeNode> queue = new ArrayList<>();
        queue.add(root);
        int index = 0;
        boolean isLeft = true;
        for (int i = 1; i < arr.length; i++) {
            if(arr[i] != null && !arr[i].equals("null")){
                TreeNode node = new TreeNode(Integer.parseInt(arr[i]));
                if(isLeft){
                    queue.get(index).left = node;
                }else {
                    queue.get(index).right = node;
                }
                queue.add(node);
            }
            if(!isLeft){
                index ++;
            }
            isLeft = !isLeft;
        }

        return root;
    }
}
